Hierarchal rate-limiting is used to control the flow of traffic streams at a network node by subjecting a traffic stream to more than one rate-limit check. The number of rate-limit checks that a traffic stream is subject to typically depends on the number of classifications to which the traffic stream belongs. For example, an Hypertext Transport Protocol (HTTP) traffic stream (i.e., a WEB traffic stream) between a WEB server and a WEB browser can be classified as ‘WEB’ traffic based upon its Transmission Control Protocol (TCP) port number. The HTTP traffic stream can also be classified as TCP traffic based upon its Internet Protocol (IP)-protocol type. Thirdly, the HTTP traffic stream can also be classified as belonging to a specific IP-subnet based upon its source and/or destination IP addresses. Additional classifications for the same traffic stream are also possible, such as those based on the physical incoming or outgoing port of the traffic, the Type of Service (TOS), Layer 2 (L2)-fields, etc.
In a hierarchal rate-limiting scheme, the traffic stream in question must satisfy rate-limit checks for all the classifications that the traffic stream falls under in order for the traffic to be deemed as having passed the overall rate check. The overall rate check is the summation of all of the rate-limit checks in a given hierarchy. For example, WEB traffic and FTP traffic may fall under separate WEB-specific and FTP-specific classifications, while also falling under a more generic TCP classification. In this case, if there are separate rate-limit checks for WEB traffic, FTP traffic, and TCP traffic, then the WEB and FTP traffic must pass their own respective rate-limit checks as well as the TCP rate limit check to be deemed as having passed the overall check.
Problems with the hierarchal rate-limiting scheme are encountered when a certain classification of traffic is oversubscribed. In software, it is possible to provide for oversubscription of certain classifications of traffic such that when a classification exceeds its own rate limit, the classification is permitted to borrow available bandwidth from the allocated rate limit of their parent classification. A parent classification is the next higher level traffic classification in a rate-limiting hierarchy. While this type of borrowing is relatively easy to implement in software, it is much more difficult to efficiently perform the same operation in hardware. Implementing a rate-limiting borrowing scheme in hardware typically requires a “series plus parallel” check on two rate-limit buckets. A difficulty with implementing series plus parallel checks in hardware is that a check on one bucket depends on the pass or fail of the other bucket. Hardware would need to go backwards (in time) to update credits for the other parallel check depending on whether the current parallel check succeeded or not. In most cases, making hardware go backwards to update credits causes additional latency for the traffic and/or additional complexity in hardware to make the credit updates happen at the desired speeds.
FIG. 1 is a functional depiction of a conventional rate-limiting hierarchy that is implemented in hardware using for example, credit buckets. In the functional depiction of FIG. 1, traffic classification B is rate-limited by rate-limit rule RB and traffic classification A is rate-limited by rate-limit rule RA. Traffic classification A is related to traffic classification B in that traffic classification A is a parent (more broad) classification with respect to traffic classification B (a child classification). Traffic in class B must pass both rate-limit checks, i.e. RA and RB, before the traffic can receive an overall pass. If a packet fails rate-limit rule RB, then the packet fails the overall rate check regardless of the outcome of the RA check. That is, regardless of whether or not there is bandwidth available in traffic classification A that could be borrowed by traffic in traffic classification B, the traffic in traffic classification B will not pass the overall rate check if the packet fails RB. Therefore, without the availability to borrow available bandwidth from parent traffic classifications, hierarchal rate-limiting schemes face severe performance limitations. While it may be possible to design complex hardware logic to achieve borrowing, complex hardware logic is not efficient in terms of chip real estate and processing resources.
Therefore, in view of the need for efficient hierarchal rate-limiting, a hardware-based bandwidth borrowing scheme is needed.